{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given \n",
    "\n",
    "$$\n",
    "V_1(s) \\le V_2(s)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*} \n",
    "B^{\\pi}(V_1)(s) - B^{\\pi}(V_2)(s) \n",
    "&= \\gamma \\sum_{s' \\in S} P_{s\\pi(s)}(s')V_1(s') - \\gamma \\sum_{s' \\in S} P_{s\\pi(s)}(s')V_2(s') \\\\\n",
    "&= \\gamma \\sum_{s' \\in S} P_{s\\pi(s)}(s') \\big(V_1(s') - V_2(s') \\big) \\\\\n",
    "&\\le 0\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus,\n",
    "\n",
    "\\begin{align*} \n",
    "B^{\\pi}(V_1)(s) \\le B^{\\pi}(V_2)(s) \n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea is to first prove $\\gamma$-contraction in the max norm\n",
    "\n",
    "$$\n",
    "\\left|\\left| B^{\\pi}(V) - B^{\\pi}(V^{\\pi}) \\right|\\right|_{\\infty} \\le \\gamma \\left|\\left| V - V^{\\pi} \\right|\\right|_{\\infty}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and then prove \n",
    "\n",
    "$$\n",
    "\\left|\\left| B^{\\pi}(V) - V^{\\pi} \\right|\\right|_{\\infty} \\le \n",
    "\\gamma \\left|\\left|V - V^{\\pi} \\right| \\right|_{\\infty}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where $B^{\\pi}$ is the Bellman operator for policy $\\pi$,\n",
    "\n",
    "$$\n",
    "B^{\\pi}(V)(s) = V'(s) + \\gamma \\sum_{s' \\in S} P_{s\\pi(s)}(s') V(s')\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The prove of $\\gamma$-contract is very similar to what I did previously in http://nbviewer.jupyter.org/github/zyxue/stanford-cs229/blob/master/Problem-set-4/5-Markov-decision-processes.ipynb. In that case, the Bellman operator has an $$\\arg \\max$ operator in it, see the discussion on https://stats.stackexchange.com/questions/324339/confusion-around-bellmen-update-operator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose \n",
    "\n",
    "$$\n",
    "\\arg\\max_{s \\in S}\\left| B^{\\pi}(V)(s^+) - B^{\\pi}(V^{\\pi})(s^+) \\right| = s^+\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\left|\\left|B^{\\pi}(V) - B^{\\pi}(V^{\\pi})\\right|\\right|_{\\infty} \n",
    "&= \\left| B^{\\pi}(V)(s^+) - B^{\\pi}(V^{\\pi})(s^+) \\right| \\\\\n",
    "&= \\left| \\gamma \\sum_{s' \\in S}P_{s^+\\pi(s)}(s')V(s') - \\gamma \\sum_{s' \\in S}P_{s^+\\pi(s')}(s')V^{\\pi}(s') \\right| \\\\\n",
    "&= \\left| \\gamma \\sum_{s' \\in S}P_{s^+ \\pi(s)}(s') \\big(V(s') - V^{\\pi}(s') \\big) \\right| \\\\\n",
    "&\\le \\gamma \\max_{s' \\in S} \\left| V(s') - V^{\\pi}(s') \\right| \\\\\n",
    "&= \\gamma \\left| \\left| V - V^{\\pi} \\right | \\right|_{\\infty}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So constantly applying $B^{\\pi}$ to $V$ will make it converge to $V^{\\pi}$, and ultimately $B^{\\pi}(V^{\\pi}) = V^{\\pi}$. Thus, we proved\n",
    "\n",
    "$$\n",
    "\\left|\\left| B^{\\pi}(V) - V^{\\pi} \\right|\\right|_{\\infty} \\le \n",
    "\\gamma \\left|\\left|V - V^{\\pi} \\right| \\right|_{\\infty}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given \n",
    "\n",
    "$$\n",
    "\\pi'(s) = \\arg \\max_{a \\in A} \\sum_{s' \\in S} P_{sa}(s') V^{\\pi}(s')\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "then\n",
    "\n",
    "\\begin{align*} \n",
    "B^{\\pi'}(V^{\\pi})(s) - B^{\\pi}(V^{\\pi})(s)\n",
    "&= \\gamma \\sum_{s' \\in S} P_{s\\pi'(s)} (s') V^{\\pi}(s') - \\gamma \\sum_{s' \\in S} P_{s\\pi(s)}(s')V^{\\pi}(s') \\\\\n",
    "&\\ge 0\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So \n",
    "\n",
    "$$\n",
    "B^{\\pi'}(V^{\\pi})(s) \\ge B^{\\pi}(V^{\\pi})(s) = V^{\\pi}(s)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Applying results from **(a)**,\n",
    "\n",
    "$$\n",
    "V^{\\pi}(s) \\le B^{\\pi'}(V^{\\pi})(s) \\le B^{\\pi'}(B^{\\pi'}(V^{\\pi}))(s) \\le \\cdots \\le V^{\\pi'})(s)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $\\pi$ keep being improved at every iteration, then it will eventually converge, given the value function has a upper bound."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
